package leetcode.graph;

import java.util.*;

/**
 * @Description: https://leetcode.cn/problems/course-schedule-ii/
 * <p>
 * 现在你总共有 numCourses 门课需要选，记为0到numCourses - 1。给你一个数组prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修bi 。
 * <p>
 * 例如，想要学习课程 0 ，你需要先完成课程1 ，我们用一个匹配来表示：[0,1] 。
 * 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
 * <p>
 * 草稿本 4
 * @Author Ammar
 * @Create 2023/6/29 10:47
 */
public class _210_课程表II {
    private Map<Integer, Vertex> vertices = new HashMap<>();

    public static void main(String[] args) {
        _210_课程表II test = new _210_课程表II();
        test.findOrder(2, new int[][]{new int[]{1, 0}});
    }

    public void createGraph(int numCourses, int[][] prerequisites) {
        for (int i = 0; i < numCourses; i++) {
            vertices.put(i, new Vertex<>(i));
        }
        for (int[] prerequisite : prerequisites) {
            Vertex from = vertices.get(prerequisite[1]);
            Vertex to = vertices.get(prerequisite[0]);
            Edge edge = new Edge<>(from, to);
            to.inEdges.add(edge);
            from.outEdges.add(edge);
        }
    }

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if (numCourses < 1) return null;
        // 存储最终排序结果
        int[] list = new int[numCourses];
        if (numCourses == 1) return list;
        createGraph(numCourses, prerequisites);

        // 存储入度为0 的顶点
        Queue<Vertex> queue = new LinkedList<>();
        Map<Vertex, Integer> ins = new HashMap<>(); // 入度会发生变化

        // 初始化队列和顶点入度的映射表
        vertices.forEach((Integer i, Vertex vertex) -> {
            int in = vertex.inEdges.size();
            if (in == 0) {
                queue.offer(vertex);
            } else {
                ins.put(vertex, in);
            }
        });

        int size = 0;
        while (!queue.isEmpty()) {
            Vertex vertex = queue.poll();
            list[size] = (int) vertex.value;
            HashSet<Edge> outEdges = (HashSet) vertex.outEdges;
            for (Edge edge : outEdges) {
                int toIn = ins.get(edge.to) - 1;
                ins.put(edge.to, toIn);
                if (toIn == 0) {
                    queue.offer(edge.to);
                }
            }
            size++;
        }
        // 效验是否有环，所有顶点的入边应该都减为0
        for (Integer count : ins.values()) {
            if (count != 0) return new int[]{};
        }
        return list;
    }

    private static class Vertex<V, E> {
        V value;
        Set<Edge<V, E>> inEdges = new HashSet<>();
        Set<Edge<V, E>> outEdges = new HashSet<>();

        Vertex(V value) {
            this.value = value;
        }

        @Override
        public boolean equals(Object obj) {
            return Objects.equals(value, ((Vertex<V, E>) obj).value);
        }

        @Override
        public int hashCode() {
            return value == null ? 0 : value.hashCode();
        }

        @Override
        public String toString() {
            return value == null ? "null" : value.toString();
        }
    }

    private static class Edge<V, E> {
        Vertex<V, E> from;
        Vertex<V, E> to;
        E weight;

        Edge(Vertex<V, E> from, Vertex<V, E> to) {
            this.from = from;
            this.to = to;
        }

        @Override
        public boolean equals(Object obj) {
            Edge<V, E> edge = (Edge<V, E>) obj;
            return Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
        }

        @Override
        public int hashCode() {
            return from.hashCode() * 31 + to.hashCode();
        }

        @Override
        public String toString() {
            return from + "->" + to + ":" + weight;
        }
    }
}